class UnionFind3 {
  constructor (size) {
    this._parent = new Array(size)
    this._rank = new Array(size) // 优化点: 基于rank的优化,记录以i为根的集合表示的树的层数(层数少的合并时指向层数多的)
    for (let i = 0; i < this._parent.length; i++) {
      this._parent[i] = i
      this._rank[i] = 1 // 初始情况各自为树,层数均为1
    }
  }

  getSize () {
    return this._parent.length
  }

  /**
   * find the number of map contains <p>
   * @param p
   * @private
   */
  _find (p) {
    if (p < 0 || p >= this.getSize()) {
      throw new Error('p is out of bound.')
    }
    while (p !== this._parent[p]) {
      this._parent[p] = this._parent[this._parent[p]] // 路径压缩: 让p指向 p父亲的父亲
      p = this._parent[p]
    }
    return p
  }

  /**
   * check that p and q belong to the same map.
   * @param p
   * @param q
   * @returns {boolean}
   */
  isConnected (p, q) {
    return this._find(p) === this._find(q)
  }

  /**
   * union p and q into one map.
   * @param p
   * @param q
   */
  unionElements (p, q) {
    const pRoot = this._find(p)
    const qRoot = this._find(q)
    if (pRoot === qRoot) {
      return
    }
    if (this._rank[pRoot] < this._rank[qRoot]) {
      this._parent[pRoot] = qRoot
    } else if (this._rank[pRoot] > this._rank[qRoot]) {
      this._parent[qRoot] = pRoot
    } else {
      // rank相等
      this._parent[pRoot] = qRoot
      this._rank[qRoot]++
    }
  }
}

export default UnionFind3
